package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 1382. 将二叉搜索树变平衡
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/16 11:18
 */
public class BalanceBST {

    private List<Integer> list = new ArrayList<>();

    public TreeNode balanceBST(TreeNode root) {
        find(root);
        return build(0, list.size() - 1);
    }

    public void find(TreeNode o) {
        if (o.left != null) {
            find(o.left);
        }
        list.add(o.val);
        if (o.right != null) {
            find(o.right);
        }
    }

    public TreeNode build(int l, int r) {
        int mid = (l + r) >> 1;
        TreeNode o = new TreeNode(list.get(mid));
        if (l <= mid - 1) {
            o.left = build(l, mid - 1);
        }
        if (mid + 1 <= r) {
            o.right = build(mid + 1, r);
        }
        return o;
    }

}
